/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        //链表为空，只有一个结点，只有两个结点，直接返回
        if(head==nullptr||head->next==nullptr||head->next->next==nullptr)
            return;
        //cur找最后一个结点
        //pre指向倒数第二个
        ListNode *pre=nullptr;
        ListNode *cur=head;
        while(cur->next)
        {
            pre=cur;
            cur=cur->next;
        }
        ListNode *sec=head->next;
        head->next=cur;
        cur->next=sec;
        pre->next=nullptr;
        reorderList(sec);
    }
};